#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int x = *p1;
	*p1 = *p2;
	*p2 = x;
}

int Getmidnums(int* a, int left, int right)
{
	int mid = left + rand() % (right - left);
	if (a[mid] < a[left])
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

void InsertSort(int* a, int n)
{
	//多次排序
	for (int i = 1; i < n; i++)
	{
		//int flag = 0;  //假设交换后数组不变

		//单趟排序，在有序区间[0,end]内排序，使数组保持有序
		int end = i - 1;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;  //找到前一个元素比较
				//flag = 1;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;   //break到此处，待插入元素比前一个大或者已经走到数组的头

		//if(flag==1)
		//PrintArry(a, n);
	}
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if ((right - left + 1) < 10)
	{
		InsertSort(a+left, right - left + 1);
	}

	//三数取中
	int mid = Getmidnums(a, left, right);
	if (left != mid)
		Swap(&a[left], &a[mid]);
	int keyi = a[left];

	int begin = left;
	int end = right;
	int cur = left + 1;
	while (cur <= end)
	{
		if (a[cur] < keyi)
		{
			Swap(&a[cur], &a[begin]);
			cur++;
			begin++;

		}
		else if (a[cur] > keyi)
		{
			Swap(&a[cur], &a[end]);
			end--;
		}
		else
		{
			cur++;
		}
	}
	
		QuickSort(a, left, begin - 1);
		QuickSort(a, end + 1, right);


}

int main()
{
	int a[] = {5,2,3,1};
	PrintArray(a, sizeof(a) / sizeof(a[0]));

	QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	PrintArray(a, sizeof(a) / sizeof(a[0]));


}